import java.util.Arrays;
import java.util.Comparator;

class Item {
    int value;
    int weight;

    Item(int value, int weight) {
        this.value = value;
        this.weight = weight;
    }

    // 计算单位重量价值
    double valuePerWeight() {
        return (double) value / weight;
    }
}

public class Knapsack {

    // 优先选取单位重量价值最大的物品
    public static double greedyByValuePerWeight(Item[] items, int capacity) {
        Arrays.sort(items, Comparator.comparingDouble(Item::valuePerWeight).reversed());

        double totalValue = 0.0;

        for (Item item : items) {
            if (capacity >= item.weight) {
                // 如果背包能装下整个物品
                capacity -= item.weight;
                totalValue += item.value;
            } else {
                // 装入部分物品
                totalValue += item.valuePerWeight() * capacity;
                break;
            }
        }
        return totalValue;
    }

    // 优先选取价值最大的物品
    public static double greedyByMaxValue(Item[] items, int capacity) {
        Arrays.sort(items, Comparator.comparingInt(item -> -item.value));

        double totalValue = 0.0;

        for (Item item : items) {
            if (capacity >= item.weight) {
                // 如果背包能装下整个物品
                capacity -= item.weight;
                totalValue += item.value;
            } else {
                // 装入部分物品
                totalValue += ((double) item.value / item.weight) * capacity;
                break;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Item[] items = {
            new Item(60, 10),
            new Item(100, 20),
            new Item(120, 30)
        };
        int capacity = 50;

        double maxValueByValuePerWeight = greedyByValuePerWeight(items, capacity);
        System.out.println("Maximum Value by Value per Weight: " + maxValueByValuePerWeight);

        double maxValueByMaxValue = greedyByMaxValue(items, capacity);
        System.out.println("Maximum Value by Max Value: " + maxValueByMaxValue);
    }
}